 //1261.在受污染的二又树中查找元素
 //https://leetcode.cn/problems/find-elements-in-a-contaminated-binary-tree/?envType=daily-question&envId=2024-03-12
class FindElements {
    void dfs(TreeNode* root) {
        if(root->left)
        {
            root->left->val = (root->val*2)+1;
            hash.insert(root->left->val);
            dfs(root->left);
        }
        if(root->right)
        {
            root->right->val = (root->val*2)+2;
            hash.insert(root->right->val);
            dfs(root->right);
        }
    }

    unordered_set<int> hash;
public:
    FindElements(TreeNode* root) {
        if(root == nullptr) return;
        root->val = 0;
        hash.insert(0);
        dfs(root);
    }

    bool find(int target) { return hash.count(target); }
};